{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Split With Minimum Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #math #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数学 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: splitNum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小和分割"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数&nbsp;<code>num</code>&nbsp;，请你将它分割成两个非负整数&nbsp;<code>num1</code> 和&nbsp;<code>num2</code>&nbsp;，满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>num1</code> 和&nbsp;<code>num2</code>&nbsp;直接连起来，得到&nbsp;<code>num</code>&nbsp;各数位的一个排列。\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>换句话说，<code>num1</code> 和&nbsp;<code>num2</code>&nbsp;中所有数字出现的次数之和等于&nbsp;<code>num</code>&nbsp;中所有数字出现的次数。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li><code>num1</code> 和&nbsp;<code>num2</code>&nbsp;可以包含前导 0 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回&nbsp;<code>num1</code> 和 <code>num2</code>&nbsp;可以得到的和的 <strong>最小</strong> 值。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>num</code>&nbsp;保证没有前导 0 。</li>\n",
    "\t<li><code>num1</code> 和&nbsp;<code>num2</code>&nbsp;中数位顺序可以与&nbsp;<code>num</code>&nbsp;中数位顺序不同。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>num = 4325\n",
    "<b>输出：</b>59\n",
    "<b>解释：</b>我们可以将 4325 分割成 <code>num1 </code>= 24 和 <code>num2 </code>= 35 ，和为 59 ，59 是最小和。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>num = 687\n",
    "<b>输出：</b>75\n",
    "<b>解释：</b>我们可以将 687 分割成 <code>num1</code> = 68 和 <code>num2 </code>= 7 ，和为最优值 75 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>10 &lt;= num &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [split-with-minimum-sum](https://leetcode.cn/problems/split-with-minimum-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [split-with-minimum-sum](https://leetcode.cn/problems/split-with-minimum-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4325', '687']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def splitNum(self, num: int) -> int:\n",
    "        digits: str = \"0123456789\"\n",
    "        count: Dict[int, int] = {d: 0 for d in digits}\n",
    "        count.update(Counter(str(num)))\n",
    "\n",
    "        asc: str = \"\".join(d * count[d] for d in digits)\n",
    "        nums: List[List[str]] = [[], []]\n",
    "        i: int = 0\n",
    "        for digit in asc:\n",
    "            nums[i % 2].append(digit)\n",
    "            i += 1\n",
    "\n",
    "        return sum(int(\"\".join(num)) for num in nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitNum(self, num: int) -> int:\n",
    "        num = ''.join(sorted(str(num)))\n",
    "        return int(num[0::2])+int(num[1::2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitNum(self, num: int) -> int:\n",
    "        s = sorted(str(num))\n",
    "        return int(\"\".join(s[::2])) + int(\"\".join(s[1::2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitNum(self, num: int) -> int:\n",
    "        lst = []\n",
    "        while num != 0:\n",
    "            lst.append(num%10)\n",
    "            num //= 10\n",
    "        if (len(lst) & 1):\n",
    "            lst.append(0)\n",
    "        lst.sort()\n",
    "        num1, num2 = 0, 0\n",
    "        while(lst):\n",
    "            num1 = num1*10 + lst.pop(0)\n",
    "            num2 = num2*10 + lst.pop(0)\n",
    "        return num1+num2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import defaultdict, Counter\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "\n",
    "# 给你一个正整数 num ，请你将它分割成两个非负整数 num1 和 num2 ，满足：\n",
    "\n",
    "# num1 和 num2 直接连起来，得到 num 各数位的一个排列。\n",
    "# 换句话说，num1 和 num2 中所有数字出现的次数之和等于 num 中所有数字出现的次数。\n",
    "# num1 和 num2 可以包含前导 0 。\n",
    "# 请你返回 num1 和 num2 可以得到的和的 最小 值。\n",
    "\n",
    "# 注意：\n",
    "\n",
    "# num 保证没有前导 0 。\n",
    "# num1 和 num2 中数位顺序可以与 num 中数位顺序不同。\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def splitNum(self, s: int) -> int:\n",
    "        # 枚举第一个数\n",
    "        chars = sorted(str(s))\n",
    "        A = chars[::2]\n",
    "        B = chars[1::2]\n",
    "        return int(\"\".join(A)) + int(\"\".join(B))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import defaultdict, Counter\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "\n",
    "# 给你一个正整数 num ，请你将它分割成两个非负整数 num1 和 num2 ，满足：\n",
    "\n",
    "# num1 和 num2 直接连起来，得到 num 各数位的一个排列。\n",
    "# 换句话说，num1 和 num2 中所有数字出现的次数之和等于 num 中所有数字出现的次数。\n",
    "# num1 和 num2 可以包含前导 0 。\n",
    "# 请你返回 num1 和 num2 可以得到的和的 最小 值。\n",
    "\n",
    "# 注意：\n",
    "\n",
    "# num 保证没有前导 0 。\n",
    "# num1 和 num2 中数位顺序可以与 num 中数位顺序不同。\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def splitNum(self, num: int) -> int:\n",
    "        # 枚举第一个数\n",
    "        res = INF\n",
    "        n = len(str(num))\n",
    "        for i in range(1 << n):\n",
    "            s1, s2 = [0], [0]\n",
    "            for j in range(n):\n",
    "                if i >> j & 1:\n",
    "                    s1.append(int(str(num)[j]))\n",
    "                else:\n",
    "                    s2.append(int(str(num)[j]))\n",
    "            s1.sort()\n",
    "            s2.sort()\n",
    "            res = min(res, int(\"\".join(map(str, s1))) + int(\"\".join(map(str, s2))))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitNum(self, num: int) -> int:\n",
    "        stnum=\"\".join(sorted(str(num)))\n",
    "        num1,num2=int(stnum[::2]),int(stnum[1::2])\n",
    "        return num1+num2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitNum(self, num: int) -> int:\n",
    "        lst = sorted(str(num))\n",
    "        n = len(lst)\n",
    "        a, b = \"\", \"\"\n",
    "        for i in range(n):\n",
    "            if i % 2 == 0:\n",
    "                a += lst[i]\n",
    "            else:\n",
    "                b += lst[i]\n",
    "        return int(a) + int(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitNum(self, num: int) -> int:\n",
    "        '''\n",
    "        拆分 num 的每一位数字，将他们排序。\n",
    "最大的两个放在个位，其次两个放十位，以此类推。注意并不需要重新组合出 num1 和 num2 ，他只要和即可。\n",
    "优化，可以不使用排序，因为只有 0 到 9 一共十个数字，只需要统计它们出现的次数，然后从 9 开始计算即可。\n",
    "        '''\n",
    "        l = []\n",
    "        while num > 0:\n",
    "            l.append(num % 10)\n",
    "            num //= 10\n",
    "        l.sort(reverse=True)\n",
    "        ans = 0\n",
    "        for i in range(len(l)):\n",
    "            ans += l[i]*10**(i // 2)\n",
    "        \n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
